home *** CD-ROM | disk | FTP | other *** search
/ C/C++ Users Group Library 1996 July / C-C++ Users Group Library July 1996.iso / listings / v_13_03 / grant / demo.cpp < prev    next >
Encoding:
C/C++ Source or Header  |  1994-12-22  |  3.7 KB  |  145 lines
  1. #include <stdlib.h>
  2. #include <stdio.h>
  3. #include "pop.h"
  4.  
  5. static enum  Bool {FALSE, TRUE};
  6.  
  7. // MAXWEIGHT defines the constraint of the knapsack
  8. // example and ItemDesc is simply the coding scheme.
  9.  
  10. static const int MAXWEIGHT = 17;
  11. static const struct 
  12. {
  13.    int   Weight;
  14.    int   Value;
  15. } ItemDesc[] = {
  16.    {3,  4}, {3,  4}, {3,  4}, {3,  4}, {3,  4},
  17.    {4,  5}, {4,  5}, {4,  5}, {4,  5},
  18.    {7, 10}, {7, 10}, {8, 11}, {8, 11}, {9, 13}};
  19.  
  20. void CalcWeightAndValue(CGAChromosome *Chromosome,
  21.                         int& Weight, int& Value);
  22. Bool FoundSolution(CGAPopulation& Pop);
  23. void PrintPop(CGAPopulation& Pop);
  24.  
  25. // Main creates the population of chromosomes and
  26. // continues creating new generations until a solution
  27. // is found.
  28.  
  29. int main(void)
  30. {
  31.    const float   MaxMutationRate = 0.2;
  32.    const int     PopulationSize  = 30;
  33.    
  34.    CGAPopulation Pop(PopulationSize, sizeof(ItemDesc) /
  35.                      sizeof(ItemDesc[0]),
  36.                      MaxMutationRate);
  37.    
  38.    while (!FoundSolution(Pop)) {
  39.       Pop.CreateNextGeneration();
  40.       PrintPop(Pop);
  41.    }
  42.    return EXIT_SUCCESS;
  43. }
  44.  
  45. // Print information and statistics about population.
  46.  
  47. void PrintPop(
  48.    CGAPopulation& Pop)
  49. {
  50.    float   TotalFitness = 0;
  51.    
  52.    printf("Idx  Fit  Val  Wt    Chromosome\n");
  53.    for (size_t ChromIdx = 0;
  54.         ChromIdx < Pop.GetPopulationSize();
  55.         ChromIdx++) {
  56.  
  57.       int   Weight;
  58.       int   Value;
  59.       CGAChromosome  *Chromosome = 
  60.          Pop.GetChromosome(ChromIdx);
  61.       
  62.       TotalFitness += Chromosome->GetFitness();
  63.       CalcWeightAndValue(Chromosome, Weight, Value);
  64.       printf("%3u %4.0f %3d %3d  ", 
  65.               ChromIdx, Chromosome->GetFitness(),
  66.               Value, Weight);
  67.       for (size_t BitIdx = 0;
  68.            BitIdx < Chromosome->GetLength();
  69.            BitIdx++) {
  70.          printf("%1u", (*Chromosome)[BitIdx]);
  71.       }
  72.       printf("\n");
  73.    }
  74.    printf(
  75.    "Gen, Best, Avg, Worst: %4d, %6.2f, %6.2f, %6.2f\n",
  76.     Pop.GetGeneration(), Pop.GetBestFitness(),
  77.     TotalFitness / ChromIdx,
  78.     Pop.GetChromosome(ChromIdx - 1)->GetFitness());
  79.    getchar();
  80. }
  81.  
  82. // Check if a solution has been found. By definition
  83. // it must have a value of ANSWER (24) and not exceed
  84. // MAXWEIGHT (17). Since the fittest chromosome could
  85. // violate the weight constraint FoundSolution must
  86. // search through the population of chromosomes.
  87.  
  88. Bool FoundSolution(
  89.    CGAPopulation& Pop)
  90. {
  91.    const int ANSWER = 24;
  92.    int       Weight;
  93.    int       Value;
  94.  
  95.    for (size_t ChromIdx = 0;
  96.         ChromIdx < Pop.GetPopulationSize();
  97.         ChromIdx++) {
  98.       CalcWeightAndValue(Pop.GetChromosome(ChromIdx),
  99.                          Weight, Value);
  100.       if (Weight <= MAXWEIGHT && Value == ANSWER) {
  101.          return TRUE;
  102.       }
  103.    }   
  104.    return FALSE;
  105. }
  106.  
  107. // Calculate the fitness of each chromosome by adding
  108. // its weight to its value then subtracting a PENALITY
  109. // for the excess weight.
  110.  
  111. float CalcFitness(
  112.    CGAChromosome *Chromosome)
  113. {
  114.    const float  PENALITY = 3.0;
  115.    int          Weight;
  116.    int          Value;
  117.  
  118.    CalcWeightAndValue(Chromosome, Weight, Value);
  119.    if (Weight > MAXWEIGHT) {
  120.       return Value - PENALITY * (Weight - MAXWEIGHT);
  121.    } else {
  122.       return Value;
  123.    }
  124. }
  125.  
  126. // Calculate the weight and valueof the chromosome by
  127. // accumulating the weight and value of each item
  128. // whose bit in the chromosome is set true.
  129.  
  130. void CalcWeightAndValue(
  131.   CGAChromosome *Chromosome,
  132.   int& Weight,
  133.   int& Value)
  134. {
  135.    Weight = 0;
  136.    Value  = 0;
  137.    for (size_t Idx = 0; Idx < Chromosome->GetLength();
  138.         Idx++) {
  139.  
  140.       if ((*Chromosome)[Idx]) {
  141.          Weight += ItemDesc[Idx].Weight;
  142.          Value  += ItemDesc[Idx].Value;
  143.       }
  144.    }
  145. }